About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
2nd International ICST Conference on Scalable Information Systems

Research Article

SDI: A Swift Tree Structure for Multi-dimensional Data Indexing in Peer-to-Peer Networks

Download918 downloads
Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.4108/infoscale.2007.908,
        author={Rong Zhang and Weining Qian and Minqi Zhou and Aoying Zhou},
        title={SDI: A Swift Tree Structure for Multi-dimensional Data Indexing in Peer-to-Peer Networks},
        proceedings={2nd International ICST Conference on Scalable Information Systems},
        proceedings_a={INFOSCALE},
        year={2010},
        month={5},
        keywords={multi-dimensional data peer-to-peer point query range query},
        doi={10.4108/infoscale.2007.908}
    }
    
  • Rong Zhang
    Weining Qian
    Minqi Zhou
    Aoying Zhou
    Year: 2010
    SDI: A Swift Tree Structure for Multi-dimensional Data Indexing in Peer-to-Peer Networks
    INFOSCALE
    ICST
    DOI: 10.4108/infoscale.2007.908
Rong Zhang1,*, Weining Qian2,*, Minqi Zhou1,*, Aoying Zhou1,*
  • 1: Computer Science and Engineering Fudan University, China
  • 2: Software Engineering Institute East China Normal University, China
*Contact email: rongzh@fudan.edu.cn, wnqian@sei.ecnu.edu.cn, zhouminqi@fudan.edu.cn, ayzhou@fudan.edu.cn

Abstract

Efficient multi-dimensional data search has received much attention in centralized systems. However, its implementation in large-scale distributed systems is not a trivial job and remains to be a challenge. In this paper, SDI, a new succinct multi-dimensional balanced tree structure based on peer-to-peer technology, is presented. With SDI structure, the query efficiency can be bounded by O(log N). Compared with previous tree-based methods, SDI has extremely low maintenance cost. This is due to the carefully chosen finger links. Furthermore, new algorithms are designed for both point query and range query processing, which make SDI free from the root-bottleneck problem. Experimental results validate the efficiency and effectiveness of the proposed approach.

Keywords
multi-dimensional data peer-to-peer point query range query
Published
2010-05-16
Modified
2011-09-11
http://dx.doi.org/10.4108/infoscale.2007.908
Copyright © 2007–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL