More Web Proxy on the site http://driver.im/

research-article

Delta: scalable data dissemination under capacity constraints

Editors: H. V. Jagadish, Aoying Zhou Authors:

Konstantinos Karanasos,

Asterios Katsifodimos,

Ioana ManolescuAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 7, Issue 4

Pages 217 - 228

https://doi.org/10.14778/2732240.2732241

Published: 01 December 2013 Publication History

Abstract

In content-based publish-subscribe (pub/sub) systems, users express their interests as queries over a stream of publications. Scaling up content-based pub/sub to very large numbers of subscriptions is challenging: users are interested in low latency, that is, getting subscription results fast, while the pub/sub system provider is mostly interested in scaling, i.e., being able to serve large numbers of subscribers, with low computational resources utilization.

We present a novel approach for scalable content-based pub/sub in the presence of constraints on the available CPU and network resources, implemented within our pub/sub system Delta. We achieve scalability by off-loading some subscriptions from the pub/sub server, and leveraging view-based query rewriting to feed these subscriptions from the data accumulated in others. Our main contribution is a novel algorithm for organizing views in a multi-level dissemination network, exploiting view-based rewriting and powerful linear programming capabilities to scale to many views, respect capacity constraints, and minimize latency. The efficiency and effectiveness of our algorithm are confirmed through extensive experiments and a large deployment in a WAN.

References

[1]

N. Bansal, R. Khandekar, and V. Nagarajan. Additive guarantees for degree-bounded directed network design. SICOMP, 2009.

[2]

R. Chand and P. Felber. Semantic peer-to-peer overlays for publish/subscribe networks. In Euro-Par, 2005.

Digital Library

[3]

A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, 1977.

Digital Library

[4]

J. Chen, D. DeWitt, F. Tian, and Y. Wang. NiagaraCQ: A scalable continuous query system for internet databases. In SIGMOD Rec., 2000.

Digital Library

[5]

P. Chirita, S. Idreos, M. Koubarakis, and W. Nejdl. Publish/Subscribe for RDF-based P2P networks. In ESWS, 2004.

[6]

D. DeHaan, P.-A. Larson, and J. Zhou. Stacked Indexed Views in Microsoft SQL Server. In SIGMOD, 2005.

Digital Library

[7]

Y. Diao, M. Altinel, M. J. Franklin, H. Zhang, and P. Fischer. Path sharing and predicate evaluation for high-performance XML filtering. TODS, 2003.

Digital Library

[8]

Y. Diao, S. Rizvi, and M. Franklin. Towards an internet-scale XML dissemination service. In VLDB, 2004.

Digital Library

[9]

P. Eades, X. Lin, and W. Smyth. A fast and effective heuristic for the feedback arc set problem. Information Processing Letters, 1993.

Digital Library

[10]

A. Gupta, O. Sahin, D. Agrawal, and A. Abbadi. Meghdoot: Content-based Publish/Subscribe over P2P networks. In Middleware, 2004.

Digital Library

[11]

H. Gupta. Selection of views to materialize in a data warehouse. In ICDT, 1997.

Digital Library

[12]

J. Hoffmann and J. Koehler. A new method to index and query sets. In JCAI, 1999.

Digital Library

[13]

M. Hong, A. Demers, J. Gehrke, C. Koch, M. Riedewald, and W. White. Massively multi-query join processing in publish/subscribe systems. In SIGMOD, 2007.

Digital Library

[14]

K. Karanasos, A. Katsifodimos, and I. Manolescu. Delta: Scalable Data Dissemination under Capacity Constraints. Inria Research Report N°8385, October 2013.

[15]

K. Karanasos, A. Katsifodimos, I. Manolescu, and S. Zoupanos. ViP2P: Efficient XML management in DHT networks. In ICWE, 2012.

Digital Library

[16]

A. Katsifodimos, I. Manolescu, and V. Vassalos. Materialized view selection for XQuery workloads. In SIGMOD, 2012.

Digital Library

[17]

L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh. Survivable network design with degree or order constraints. SICOMP, 2009.

Digital Library

[18]

I. Manolescu, K. Karanasos, V. Vassalos, and S. Zoupanos. Efficient XQuery rewriting using multiple views. In ICDE, 2011.

Digital Library

[19]

I. Miliaraki and M. Koubarakis. Foxtrot: Distributed structural and value XML filtering. ACM TWEB, 2012.

Digital Library

[20]

O. Papaemmanouil. SemCast: Semantic multicast for content-based data dissemination. In ICDE, 2005.

Digital Library

[21]

R. Pottinger and A. Y. Halevy. MiniCon: A scalable algorithm for answering queries using views. VLDB J., 10(2-3), 2001.

Digital Library

[22]

K. A. Ross, D. Srivastava, and S. Sudarshan. Materialized view maintenance and integrity constraint checking: trading space for time. In SIGMOD, 1996.

Digital Library

[23]

A. Schmidt, F. Waas, M. L. Kersten, M. J. Carey, I. Manolescu, and R. Busse. XMark: A Benchmark for XML Data Management. In VLDB, 2002.

Digital Library

[24]

A. Segev and W. Fang. Currency-based updates to distributed materialized views. In ICDE, 1990.

Digital Library

[25]

N. Tang, J. X. Yu, M. T. Özsu, B. Choi, and K.-F. Wong. Multiple Materialized View Selection for XPath Query Rewriting. In ICDE, 2008.

Digital Library

[26]

W. W. Terpstra, S. Behnel, L. Fiege, A. Zeidler, and A. P. Buchmann. A peer-to-peer approach to content-based publish/subscribe. In DEBS, 2003.

Digital Library

[27]

F. Tian, B. Reinwald, H. Pirahesh, T. Mayr, and J. Myllymaki. Implementing a scalable XML publish/subscribe system using relational database systems. In ACM SIGMOD, 2004.

Digital Library

[28]

X. Wu, D. Theodoratos, and W. H. Wang. Answering XML queries using materialized views revisited. In CIKM, 2009.

Digital Library

[29]

Gurobi Optimizer. http://www.gurobi.com, 2013.

Cited By

Liu RPark KPsallidas FZhu XMo JSen RInterlandi MKaranasos KTian YCamacho-Rodríguez J(2023)Optimizing Data Pipelines for Machine Learning in Feature StoresProceedings of the VLDB Endowment10.14778/3625054.362506016:13(4230-4239)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.14778/3625054.3625060
Sahu SSalihoglu SLi GLi ZIdreos SSrivastava D(2021)GraphsurgeProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452837(1518-1530)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452837
Sebaa ANouicer ATari A(2019)Impact of technology evolution on the materialised viewsInternational Journal of Business Information Systems10.1504/ijbis.2019.09930530:4(427-462)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1504/ijbis.2019.099305
Show More Cited By

Recommendations

Journal self-citation study for semiconductor literature: synchronous and diachronous approach
Special issue: Informetrics

The present study investigates the self-citations of the most productive semiconductor journals by synchronous (self-citing rate) and diachronous (self-cited rate) approaches. Journal's productivity of 100 most productive semiconductor journals was ...
Team size and retracted citations reveal the patterns of retractions from 1981 to 2020
Abstract
The growth of the retraction databases reveals the disturbing trend in science and also the rising trend of citations of retracted papers is a serious concern. The objective of the study is to investigate the patterns of retractions through the ...
Collaborative interdisciplinary astrobiology research: a bibliometric study of the NASA Astrobiology Institute

This study aims to undertake a bibliometric investigation of the NASA Astrobiology Institute (NAI) funded research that was published between 2008 and 2012 (by teams of Cooperative Agreement Notice Four and Five). For this purpose, the study creates an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 7, Issue 4

December 2013

112 pages

ISSN:2150-8097

Editors:
H. V. Jagadish
University of Michigan
,
Aoying Zhou
East Normal University, China

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 December 2013

Published in PVLDB Volume 7, Issue 4

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
21
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu RPark KPsallidas FZhu XMo JSen RInterlandi MKaranasos KTian YCamacho-Rodríguez J(2023)Optimizing Data Pipelines for Machine Learning in Feature StoresProceedings of the VLDB Endowment10.14778/3625054.362506016:13(4230-4239)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.14778/3625054.3625060
Sahu SSalihoglu SLi GLi ZIdreos SSrivastava D(2021)GraphsurgeProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452837(1518-1530)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452837
Sebaa ANouicer ATari A(2019)Impact of technology evolution on the materialised viewsInternational Journal of Business Information Systems10.1504/ijbis.2019.09930530:4(427-462)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1504/ijbis.2019.099305
Sebaa ATari A(2019)Materialized View Maintenance: Issues, Classification, and Open ChallengesInternational Journal of Cooperative Information Systems10.1142/S021884301930001828:01(1930001)Online publication date: 3-Apr-2019
https://doi.org/10.1142/S0218843019300018
Wingerath WRitter NGessert FWingerath WRitter NGessert F(2019)Data Stream ManagementReal-Time & Stream Data Management10.1007/978-3-030-10555-6_4(43-55)Online publication date: 3-Jan-2019
https://doi.org/10.1007/978-3-030-10555-6_4
Jindal AKaranasos KRao SPatel H(2018)Selecting subexpressions to materialize at datacenter scaleProceedings of the VLDB Endowment10.14778/3192965.319297111:7(800-812)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.14778/3192965.3192971
Carbone PGévay GHermann GKatsifodimos ASoto JMarkl VHaridi S(2017)Large-Scale Data Stream Processing SystemsHandbook of Big Data Technologies10.1007/978-3-319-49340-4_7(219-260)Online publication date: 26-Feb-2017
https://doi.org/10.1007/978-3-319-49340-4_7
Camacho-Rodríguez JColazzo DHerschel MManolescu IRoy Chowdhury SMukhopadhyay SZhai CBertino ECrestani FMostafa JTang JSi LZhou XChang YLi YSondhi P(2016)Reuse-based Optimization for Pig LatinProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983669(2215-2220)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2983323.2983669
Basık FGedik BFerhatosmanoğlu HKalender M(2015)S$$^3$$3-TMThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-015-0404-324:6(849-866)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s00778-015-0404-3

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents