Sorry I didn't make it clear but these are titles of academic papers pretty easily findable on Google Scholar.
-B On Nov 8, 2007 12:43 PM, Brandon Martin-Anderson <[EMAIL PROTECTED]> wrote: > Oh you better believe Google has thought about things like bike routing: > the 'avoid highways' checkbox is their nod to it. But they're a mass-market > company and there's no mass-market for bicycle routing (yet!) > > A year ago I did a bit of research and came up with the following notes on > heirarcical encoding for shortest-path approximation on very large graphs, > which I strongly suspect is the technology Google has expanded upon to > create their system. Here are my a few things I wanted to follow up on, > unedited and unordered: > > Heirarchical Optimizations of Optimal Path Finding for Transportation > Applications > 1996 foundational text outlining HEPV (heirarchical encoded path > views). > See: ref 13 for algorithm on graph partitioning, multi-levels > > Heirarchical Encoded Path Views... > 1998 expansion of (1) much more readable, prettier graphs > > A Performance Analysis... > 1997 analysis of a 2-level heirarchical graph, with 10x as many nodes > in the test graph as (1) > > Approximate Shortest-path Algorithms > post-2002. Proposes a "Network Tree Model" as an alternative to HEPV > for extremely large networks (millions of nodes). Results are not optimal. > > Approximating Shortest-Paths in Large Scale Networks > 1998 proposition of a non-optimal heirarchical graph system > > An efficeint path computation model for heirarchically structured... > 1998/2000 proposed heirarchical search method uses much less space > than HEPV. Touches base on storage methods, recommends [ > 40<http://scholar.google.com/scholar?hl=en&lr=&q=CCAM%253A+shekhar&btnG=Search>]. > Also As this is a major heirarchical paper search things that reference > it<http://scholar.google.com/scholar?hl=en&lr=&cites=5835360768894073554>. > One 2006 paper on speed-up has been added. > > Combining Speed-up Techniques > shortest path for trains and busses: see > "FATES: Finding A Time dEpendent Shortest path" > > I have a little more and I'll elaborate when I get some time. > > -B > > > > On Nov 8, 2007 12:21 PM, Gerald A <[EMAIL PROTECTED] > wrote: > > > I'm a relative newbie in the mapping domain, so this might be old news > > to some, > > but it caught my eye: > > http://googleblog.blogspot.com/2007/11/road-to-better-path-finding.html > > > > While we don't have access to some of the resources of Google, if we > > can use what they've learned to simplify or speed up our routing, that > > can't hurt, can it? (I'm sure they haven't thought about things like > > bike specific routing, but if they are discussing general routing > > techniques then that should still help). > > > > Gerald. > > > > _______________________________________________ > > Routing mailing list > > [email protected] > > http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing > > > >
_______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
