Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Range queries in trie-structured overlays
 
conference paper

Range queries in trie-structured overlays

Datta, Anwitaman  
•
Hauswirth, Manfred  
•
John, Renault
Show more
2005
Fifth IEEE International Conference on Peer-to-Peer Computing (P2P'05)
The Fifth IEEE International Conference on Peer-to-Peer Computing

Among the open problems in P2P systems, support for non-trivial search predicates, standardized query languages, distributed query processing, query load balancing, and quality of query results have been identified as some of the most relevant issues. This paper describes how range queries as an important non-trivial search predicate can be supported in a structured overlay network that provides $O(\log{n})$ search complexity on top of a trie abstraction. We provide analytical results that show that the proposed approach is efficient, supports arbitrary granularity of ranges, and demonstrate that its algorithmic complexity in terms of messages is independent of the size of the queried ranges and only depends on the size of the result set. In contrast to other systems which provide evaluation results only through simulations, we validate the theoretical analysis of the algorithms with large-scale experiments on the PlanetLab infrastructure using a fully-fledged implementation of our approach.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

Datta05RangeQueries.pdf

Access type

openaccess

Size

278.91 KB

Format

Adobe PDF

Checksum (MD5)

e32785fbd79d79ec03b9db21ec051a44

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés