On indexed data broadcast

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On indexed data broadcast

Full text

Pdf (1.27 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 463 - 472

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Sanjeev Khanna	Dept. of Fundamental Mathematics Research, Bell Laboratories, 700 Mountain Avenue, Murray Hill, NJ
Shiyu Zhou	Dept. of Fundamental Mathematics Research, Bell Laboratories, 700 Mountain Avenue, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 19, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276859 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
	2	M. A~iAR, J.WoNG, ~ On the optimality of cyclic transmission in Teletext Systems", IEEE Trans. Comm. 35 (11), 1987. pp 1159-1170.
	3	S. ANn.Y, (3. GLASS, R.Hxssn~, 'The scheduling of maintenance service", submitted for publication, 1996
	4	Amotz Bar-Noy , Randeep Bhatia , Joseph Naor , Baruch Schieber, Minimizing service and operation costs of periodic scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 25-27, 1998, San Francisco, California, United States
	5	R. BAYER, "Symmetric binary B-trees: data structure and maintenance algorithms", Acta Informatica 1, 1972. pp 290-306.
	6	A. BESTAVP. OS AND C. CUre,A, ~Server-Initiated Document Dissemination for the WWW", IEEE Dat En. gineerin# Bulletin, September 1996.
	7	T. F. Bowen , G. Gopal , G. Herman , T. Hickey , K. C. Lee , W. H. Mansfield , J. Raitz , A. Weinrib, The Datacycle architecture, Communications of the ACM, v.35 n.12, p.71-81, Dec. 1992 [doi>10.1145/138859.138868]
	8	M. CHAN, F. CHIN, "Schedulers for larger classes of pinwheel instances", Algorithrnica (9), 1996. pp 425- 462.
	9	D. Gn:Fom) ET AL., '~The application of digital broadcast communication systems", Stanford University Tech. Reprot, 199~.
	10	(3. GLASS, "Feasibility of scheduling lot sizes of two frequencies on one machine", European Journal of OR 75, 1994. pp 354-364.
	11	L. GUIBAS AND R. SEDGEWICK, ~A dichromatic framework for balanced tree/', IEEE FOCS, 1978. pp 8-21.
	12	Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States
	13	Robert Holte , Louis Rosier , Igor Tulchinsky , Donald Varvel, Pinwheel scheduling with two distinct numbers, Theoretical Computer Science, v.100 n.1, p.105-135, June 22, 1992 [doi>10.1016/0304-3975(92)90365-M]
	14	Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
	15	R. Jain , J. Werth, Airdisks and AirRAID: Modeling and scheduling periodic wireless data broadcast, Certer for Discrete Mathematics & Theoretical Computer Science, 1995
	16	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	17	William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
	18	N. Smv~o.~ Am) S. VEm{ATASW~~, Ener~y-effident inde.~dng for information dissemi~atlon in wireless systems. A CM-Baltzer Journal of Mobile Networks and Nomadic Applications (MONET), December 1996.
	19	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	20	S. So, L. TASS~A$, "Broadcast scheduling for information distribution", IIVFOCOM, 1997.
	21	W. WEI, C. Liu, "On a periodic maintenance problem', OR Letters 2, 1983. pp 90-93.
	22	Nitin Vaidya , Sohail Hameed, Improved Algorithms for Scheduling Data Broadcast, Texas A & M University, College Station, TX, 1996

CITED BY 11

	Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly-periodic schedules, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.107-116, August 2001, Newport, Rhode Island, United States
	Claire Kenyon , Nicolas Schabanel , Neal Young, Polynomial-time approximation scheme for data broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.659-666, May 21-23, 2000, Portland, Oregon, United States
	Claire Kenyon , Nicolas Schabanel, The data broadcast problem with non-uniform transmission times, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 17-19, 1999, Baltimore, Maryland, United States
	Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly periodic schedules, Distributed Computing, v.15 n.4, p.207-220, December 2002
	Zvika Brakerski , Aviv Nisgav , Boaz Patt-Shamir, General perfectly periodic scheduling, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Zvika Brakerski , Vladimir Dreizin , Boaz Patt-Shamir, Dispatching in perfectly-periodic schedules, Journal of Algorithms, v.49 n.2, p.219-239, November 2003
	Wai Gen Yee , Shamkant B. Navathe, Efficient data access to multi-channel broadcast programs, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Vincenzo Liberatore, Caching and Scheduling for Broadcast Disk Systems, Journal of Experimental Algorithmics (JEA), 6, p.5-es, 2001
	Amotz Bar-Noy , Vladimir Dreizin , Boaz Patt-Shamir, Efficient algorithms for periodic scheduling, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.2, p.155-173, 5 June 2004
	Vincenzo Liberatore, Circular arrangements and cyclic broadcast scheduling, Journal of Algorithms, v.51 n.2, p.185-215, May 2004
	Jianliang Xu , Wang-Chien Lee , Xueyan Tang, Exponential index: a parameterized distributed indexing scheme for data on air, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA