Publication Date:
2012-09-29
Description:
This work introduces decentralized query processing techniques based on MIDAS, a novel distributed multidimensional index. In particular, MIDAS implements a distributed k-d tree, where leaves correspond to peers, and internal nodes dictate message routing. MIDAS requires that peers maintain little network information, and features mechanisms that support fault tolerance and load balancing. The proposed algorithms process point and range queries over the multidimensional indexed space in only O (log n ) hops in expectance, where n is the network size. For nearest neighbor queries, two processing alternatives are discussed. The first, termed eager processing, has low latency (expected value of O (log n ) hops) but may involve a large number of peers. The second, termed iterative processing, has higher latency (expected value of O (log 2 n ) hops) but involves far fewer peers. A detailed experimental evaluation demonstrates that our query processing techniques outperform existing methods for settings involving real spatial data as well as in the case of high dimensional synthetic data. Content Type Journal Article Pages 1-31 DOI 10.1007/s10707-012-0163-x Authors George Tsatsanifos, National Technical University of Athens, Athens, Greece Dimitris Sacharidis, Institute for the Management of Information Systems, R.C. “Athena”, Athens, Greece Timos Sellis, National Technical University of Athens, Athens, Greece Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175
Print ISSN:
1384-6175
Electronic ISSN:
1573-7624
Topics:
Geography
