Article

Locating data sources in large distributed systems

Authors:

Leonidas Galanis,

Shawn R. Jeffery,

David J. DeWittAuthors Info & Claims

VLDB '03: Proceedings of the 29th international conference on Very large data bases - Volume 29

Pages 874 - 885

Published: 09 September 2003 Publication History

Abstract

Querying large numbers of data sources is gaining importance due to increasing numbers of independent data providers. One of the key challenges is executing queries on all relevant information sources in a scalable fashion and retrieving fresh results. The key to scalability is to send queries only to the relevant servers and avoid wasting resources on data sources which will not provide any results. Thus, a catalog service, which would determine the relevant data sources given a query, is an essential component in efficiently processing queries in a distributed environment. This paper proposes a catalog framework which is distributed across the data sources themselves and does not require any central infrastructure. As new data sources become available, they automatically become part of the catalog service infrastructure, which allows scalability to large numbers of nodes. Furthermore, we propose techniques for workload adaptability. Using simulation and real-world data we show that our approach is valid and can scale to thousands of data sources.

References

[1]

{1} A. Aboulnaga, A. R. Alameldeen, J. F. Naughton. Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. VLDB 2001.

Digital Library

[2]

{2} P. Albitz, C. Liu. DNS and BIND. (4th Ed.) O'Reilly and Associates, 2001.

Digital Library

[3]

{3} B. H. Bloom. Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, July 1970.

Digital Library

[4]

{4} R. Braumandl, M. Keidl, A. Kemper, D. Kossmann, A. Kreutz, S. Seltzsam, K. Stocker. ObjectGlobe: Ubiquitous query processing on the Internet. VLDB Journal 10(1): 48-71 (2001).

Digital Library

[5]

{5} B. Choi, What are Real DTDs Like. WebDB 2002.

[6]

{6} A. Crespo, H. Garcia-Molina. Routing Indices for Peer-to-Peer Systems, ICDCS 2002.

Digital Library

[7]

{7} F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica. Wide-area cooperative storage with CFS. SOSP 2001.

Digital Library

[8]

{8} FreeNet: http://www.freenetproject.org

[9]

{9} Gnutella Resources. http://gnutella.wego.com/

[10]

{10} L. Galanis, Y. Wang, S. R. Jeffery, D. J. DeWitt. Processing Queries in a Large Peer-to-Peer System. CAiSE 2003 (to appear)

Digital Library

[11]

{11} J. Gray, P. Helland, P. O' Neill, D. Shasha. The Dangers of Replication and a Solution. Readings In Database Systems, 3rd edition p372.

Digital Library

[12]

{12} M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, I. Stoica. Complex Queries in DHT-based Peer-to-Peer Networks. IPTPS '02.

Digital Library

[13]

{13} Y. Ioannidis, V. Poosala. Histogram-Based Solutions to Diverse Database Estimation Problems. Data Engineering Bulletin 18(3).

[14]

{14} L. Kleinrock. Queueing Systems, Volume 1: Theory, John Wiley & Sons, New York, 1975.

Digital Library

[15]

{15} J. Kubiatowicz et al. OceanStore: An Architecture for Global-Scale Persistent Storage. In Proc. ASPLOS 2000.

Digital Library

[16]

{16} W. Litwin, M. Neimat, D. A. Schneider: LH^* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336

Digital Library

[17]

{17} Napster. http://www.napster.com

[18]

{18} M. T. Özsu, P. Valduriez. Principles of Distributed Database Systems, Second Edition. Prentice-Hall 1999.

Digital Library

[19]

{19} N. Polyzotis, M. N. Garofalakis. Structure and Value Synopses for XML Data Graphs. VLDB 2002.

Digital Library

[20]

{20} V. Papadimos, D. Maier, K. Tufte. Distributed Query Processing and Catalogs for Peer-to-Peer Systems. CIDR 2003

[21]

{21} S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Schenker. A Scalable Content-Addressable Network. in Proc. of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications.

Digital Library

[22]

{22} A. Rowstron, P. Druschel, Pastry. Scalable, distributed object location and routing for large-scale peer-to-peer systems. IFIP/ACM Intl. Conference on Distributed Systems Platforms.

Digital Library

[23]

{23} A. Rowstron, P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. SOSP 2001.

Digital Library

[24]

{24} S. Saroiu, P. K. Gummadi, S. Gribble. Exploring the Design Space of Distributed and Peer-to-Peer Systems: Comparing the Web, TRIAD, and Chord/CFS. IPTPS '02

Digital Library

[25]

{25} I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proc. SIGCOMM 2001.

Digital Library

[26]

{26} TPC-C Benchmark Standard Specification Revision 5.0.

[27]

{27} S. Waterhouse. JXTA Search: Distributed Search for Distributed Networks. White Paper http://search.jxta.org

[28]

{28} R. Williams, D. Daniels, L. Haas, G. Lapis, B. Linsey, P. Ng, R. Obermarck, P. Selinger, A. Walker, P. Wilms, R. Yost. R^*: An Overview of the Architecture. IBM Research Report RJ3325.

[29]

{29} XML Path Language (XPath) 2.0 http://www.w3.org/TR/xpath20/

[30]

{30} B. Yang, H. Garcia-Molina. Efficient Search in peer-to-peer networks. In Proc. ICDCS 2002.

Digital Library

[31]

{31} B. Yang, H. Garcia-Molina. Designing a Super-Peer Network, In Proc. ICDE 2003.

[32]

{32} B. Y. Zhao, J. Kubiatowicz, A. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. UCB Tech. Report UCB/CSD-01-1141.

Cited By

Comito CTalia DTrunfio P(2016)A distributed selectivity-driven search strategy for semi-structured data over DHT-based networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.03.01593:C(10-29)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.03.015
Camacho-Rodríguez JColazzo DManolescu IGuerrini GPaton N(2013)Web data indexing in the cloudProceedings of the 16th International Conference on Extending Database Technology10.1145/2452376.2452382(41-52)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2452376.2452382
Slavov VRao PPaturi SSwami TBarnes MRao DPalvai R(2013)A new tool for sharing and querying of clinical documents modeled using HL7 Version 3 standardComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2013.07.002112:3(529-552)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.cmpb.2013.07.002
Show More Cited By

Index Terms

Locating data sources in large distributed systems
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
      2. Parallel and distributed DBMSs
  2. Information retrieval
    1. Document representation
    2. Evaluation of retrieval results
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Querying distributed RDF data sources with SPARQL
ESWC'08: Proceedings of the 5th European semantic web conference on The semantic web: research and applications

Integrated access to multiple distributed and autonomous RDF data sources is a key challenge for many semantic web applications. As a reaction to this challenge, SPARQL, the W3C Recommendation for an RDF query language, supports querying of multiple RDF ...
Identifying Data Sources for Data Warehouses
IDEAL '02: Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning

In order to establish a useful data warehouse, it must be correct and consistent. Hence, when selecting the data sources for building the data warehouse, it is essential know exactly about the concept and structure of all possible data sources and the ...
Scaling Access to Heterogeneous Data Sources with DISCO

Accessing many data sources aggravates problems for users of heterogeneous distributed databases. Database administrators must deal with fragile mediators, that is, mediators with schemas and views that must be significantly changed to incorporate a new ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

VLDB '03: Proceedings of the 29th international conference on Very large data bases - Volume 29

September 2003

1134 pages

ISBN:0127224424

Sponsors

VLDB Endowment: Very Large Database Endowment

Publisher

VLDB Endowment

Publication History

Published: 09 September 2003

Qualifiers

Article

Conference

VLDB '03

Sponsor:

VLDB Endowment

VLDB '03: Very large data bases

September 9 - 12, 2003

Berlin, Germany

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Comito CTalia DTrunfio P(2016)A distributed selectivity-driven search strategy for semi-structured data over DHT-based networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.03.01593:C(10-29)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.03.015
Camacho-Rodríguez JColazzo DManolescu IGuerrini GPaton N(2013)Web data indexing in the cloudProceedings of the 16th International Conference on Extending Database Technology10.1145/2452376.2452382(41-52)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2452376.2452382
Slavov VRao PPaturi SSwami TBarnes MRao DPalvai R(2013)A new tool for sharing and querying of clinical documents modeled using HL7 Version 3 standardComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2013.07.002112:3(529-552)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.cmpb.2013.07.002
Miliaraki IKoubarakis M(2012)FoXtrotACM Transactions on the Web10.1145/2344416.23444196:3(1-34)Online publication date: 2-Oct-2012
https://dl.acm.org/doi/10.1145/2344416.2344419
Rao PKomara Swami TRao DBarnes MThorve SNatoo PLuo GLiu JYang C(2012)A software tool for large-scale sharing and querying of clinical documents modeled using HL7 version 3 standardProceedings of the 2nd ACM SIGHIT International Health Informatics Symposium10.1145/2110363.2110417(473-482)Online publication date: 28-Jan-2012
https://dl.acm.org/doi/10.1145/2110363.2110417
Karanasos KKatsifodimos AManolescu IZoupanos S(2012)ViP2PProceedings of the 12th international conference on Web Engineering10.1007/978-3-642-31753-8_32(386-394)Online publication date: 23-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31753-8_32
Liu JFan W(2011)Polymorphic queries for P2P systemsInformation Systems10.1016/j.is.2011.01.00136:5(825-842)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1016/j.is.2011.01.001
Rao PEdlavitch SHackman JHickman TMcNair DRao DÇatalyürek ÜLuo GAndrade HSmalheiser N(2010)Towards large-scale sharing of electronic health records of cancer patientsProceedings of the 1st ACM International Health Informatics Symposium10.1145/1882992.1883081(545-549)Online publication date: 11-Nov-2010
https://dl.acm.org/doi/10.1145/1882992.1883081
Comito CTalia DTrunfio PDesai BBernardino J(2010)Selectivity-based XML query processing in structured peer-to-peer networksProceedings of the Fourteenth International Database Engineering & Applications Symposium10.1145/1866480.1866513(236-244)Online publication date: 16-Aug-2010
https://dl.acm.org/doi/10.1145/1866480.1866513
Curtmola EDeutsch ARamakrishnan KSrivastava DElmagarmid AAgrawal D(2010)Load-balanced query dissemination in privacy-aware online communitiesProceedings of the 2010 ACM SIGMOD International Conference on Management of data10.1145/1807167.1807219(471-482)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807167.1807219
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents