@conference {16840,
	title = {Scalable network distance browsing in spatial databases},
	booktitle = {Proceedings of the 2008 ACM SIGMOD international conference on Management of data},
	series = {SIGMOD {\textquoteright}08},
	year = {2008},
	month = {2008///},
	pages = {43 - 54},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {An algorithm is presented for finding the k nearest neighbors in a spatial network in a best-first manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encoding that takes advantage of the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Thus, in the worst case, the amount of work depends on the number of objects that are examined and the number of links on the shortest paths to them from q, rather than depending on the number of vertices in the network. The amount of storage required to keep track of the subsets is reduced by taking advantage of their spatial coherence which is captured by the aid of a shortest path quadtree. In particular, experiments on a number of large road networks as well as a theoretical analysis have shown that the storage has been reduced from O(N3) to O(N1.5) (i.e., by an order of magnitude equal to the square root). The precomputation of the shortest paths along the network essentially decouples the process of computing shortest paths along the network from that of finding the neighbors, and thereby also decouples the domain S of the query objects and that of the objects from which the neighbors are drawn from the domain V of the vertices of the spatial network. This means that as long as the spatial network is unchanged, the algorithm and underlying representation of the shortest paths in the spatial network can be used with different sets of objects.},
	keywords = {decoupling, nearest neighbor, scalability, shortest path quadtree, spatial networks},
	isbn = {978-1-60558-102-6},
	doi = {10.1145/1376616.1376623},
	url = {http://doi.acm.org/10.1145/1376616.1376623},
	author = {Samet, Hanan and Sankaranarayanan,Jagan and Alborzi,Houman}
}
@conference {16870,
	title = {Distance join queries on spatial networks},
	booktitle = {Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems},
	series = {GIS {\textquoteright}06},
	year = {2006},
	month = {2006///},
	pages = {211 - 218},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {The result of a distance join operation on two sets of objects R, S on a spatial network G is a set P of object pairs pq, p {\'E} R, q {\'E} S such that the distance of an object pair pq is the shortest distance from p to q in G. Several variations to the distance join operation such as UnOrdered, Incremental, topk, Semi-Join impose additional constraints on the distance between the object pairs in P, the ordering of object pairs in P, and on the cardinality of P. A distance join algorithm on spatial networks is proposed that works in conjunction with the SILC framework, which is a new approach to query processing on spatial networks. Experimental results demonstrate up to an order of magnitude speed up when compared with a prominent existing technique.},
	keywords = {location-based services, path coherence, Query processing, SILC framework, Spatial databases, spatial networks},
	isbn = {1-59593-529-0},
	doi = {10.1145/1183471.1183506},
	url = {http://doi.acm.org/10.1145/1183471.1183506},
	author = {Sankaranarayanan,Jagan and Alborzi,Houman and Samet, Hanan}
}
@conference {16879,
	title = {Efficient query processing on spatial networks},
	booktitle = {Proceedings of the 13th annual ACM international workshop on Geographic information systems},
	series = {GIS {\textquoteright}05},
	year = {2005},
	month = {2005///},
	pages = {200 - 209},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {A framework for determining the shortest path and the distance between every pair of vertices on a spatial network is presented. The framework, termed SILC, uses path coherence between the shortest path and the spatial positions of vertices on the spatial network, thereby, resulting in an encoding that is compact in representation and fast in path and distance retrievals. Using this framework, a wide variety of spatial queries such as incremental nearest neighbor searches and spatial distance joins can be shown to work on datasets of locations residing on a spatial network of sufficiently large size. The suggested framework is suitable for both main memory and disk-resident datasets.},
	keywords = {location-based services, path coherence, Query processing, SILC framework, Spatial databases, spatial networks},
	isbn = {1-59593-146-5},
	doi = {10.1145/1097064.1097093},
	url = {http://doi.acm.org/10.1145/1097064.1097093},
	author = {Sankaranarayanan,Jagan and Alborzi,Houman and Samet, Hanan}
}
