[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/order-maintenance-problem-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/order-maintenance-problem-wikipedia\/","headline":"Order-maintenance problem – Wikipedia","name":"Order-maintenance problem – Wikipedia","description":"In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations: insert(X, Y), which inserts","datePublished":"2022-05-08","dateModified":"2022-05-08","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/aae0f22048ba6b7c05dbae17b056bfa16e21807d","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/aae0f22048ba6b7c05dbae17b056bfa16e21807d","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/order-maintenance-problem-wikipedia\/","wordCount":6820,"articleBody":"In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations:insert(X, Y), which inserts X immediately after Y in the total order;order(X, Y), which determines if X precedes Y in the total order; anddelete(X), which removes X from the set.Paul Dietz first introduced a data structure to solve this problem in1982.[1] This datastructure supports insert(X, Y) in O(log\u2061n){displaystyle O(log n)} (in Big O notation)amortized time and order(X, Y) in constant time but doesnot support deletion. Athanasios Tsakalidis used BB[\u03b1] trees with the same performance bounds that supportsdeletion in O(log\u2061n){displaystyle O(log n)} and improved insertion and deletion performance toO(1){displaystyle O(1)} amortized time with indirection.[2] Dietz and Daniel Sleator published an improvement to worst-case constant time in 1987.[3] Michael Bender, Richard Cole and Jack Zito published significantly simplified alternatives in 2004.[4] Bender, Fineman, Gilbert, Kopelowitz and Montes also published a deamortized solution in 2017.[5]Efficient data structures for order-maintenance have applications inmany areas, including data structure persistence,[6] graph algorithms[7][8] and fault-tolerant data structures.[9]Table of ContentsList labeling[edit]O(1) amortized insertion via indirection[edit]Order[edit]Insert[edit]Delete[edit]References[edit]External links[edit]List labeling[edit]A problem related to the order-maintenance problem is thelist-labeling problem in which instead of the order(X,Y) operation the solution must maintain an assignment of labelsfrom a universe of integers {1,2,\u2026,m}{displaystyle {1,2,ldots ,m}} to theelements of the set such that X precedes Y in the total order if andonly if X is assigned a lesser label than Y. It must also support anoperation label(X) returning the label of any node X.Note that order(X, Y) can be implemented simply bycomparing label(X) and label(Y) so that anysolution to the list-labeling problem immediately gives one to theorder-maintenance problem. In fact, most solutions to theorder-maintenance problem are solutions to the list-labeling problemaugmented with a level of data structure indirection to improveperformance. We will see an example of this below.For a list-labeling problem on sets of size up to n{displaystyle n}, the cost of list labeling depends on how large m{displaystyle m} is a function of n{displaystyle n}.  The relevant parameter range for order maintenance are for m=n1+\u0398(1){displaystyle m=n^{1+Theta (1)}}, for which an O(log\u2061n){displaystyle O(log n)} amortized cost solution is known,[10] and 2\u03a9(n){displaystyle 2^{Omega (n)}} for which a constant time amortized solution is known[11]O(1) amortized insertion via indirection[edit]Indirection is a technique used in data structures in which a problemis split into multiple levels of a data structure in order to improveefficiency. Typically, a problem of size n{displaystyle n} is split inton\/log\u2061n{displaystyle n\/log n} problems of size log\u2061n{displaystyle log n}. Forexample, this technique is used in y-fast tries. Thisstrategy also works to improve the insertion and deletion performanceof the data structure described above to constant amortized time. Infact, this strategy works for any solution of the list-labelingproblem with O(log\u2061n){displaystyle O(log n)} amortized insertion and deletiontime.  The order-maintenance data structure with indirection.  The total order elements are stored in O(N\/log\u2061N){displaystyle O(N\/log N)} contiguous sublists of size O(log\u2061N){displaystyle O(log N)}, each of which has a representative in the scapegoat tree.The new data structure is completely rebuilt whenever it grows toolarge or too small. Let N{displaystyle N} be the number of elements ofthe total order when it was last rebuilt. The data structure isrebuilt whenever the invariant N3\u2264n\u22642N{displaystyle {tfrac {N}{3}}leq nleq 2N} isviolated by an insertion or deletion. Since rebuilding can be done inlinear time this does not affect the amortized performance ofinsertions and deletions.During the rebuilding operation, the N{displaystyle N} elements of thetotal order are split into O(N\/log\u2061N){displaystyle O(N\/log N)} contiguoussublists, each of size \u03a9(log\u2061N){displaystyle Omega (log N)}. The list labeling problem is solved on the setset of nodes representing each ofthe sublists in their original list order. The labels for this subproblem are taken to be polynomial — say m=N2{displaystyle m=N^{2}}, so that they can be compared in constant time and updated in amortized O(log\u2061N){displaystyle O(log N)} time.For each sublist adoubly-linked list of its elements is built storing with each element apointer to its representative in the tree as well as a local integerlabel. The local integer labels are also taken from a range m=N2{displaystyle m=N^{2}}, so that the can be compared in constant time, but because each local problem involves only \u0398(log\u2061N){displaystyle Theta (log N)} items, the labels range m{displaystyle m} is exponential in the number of items being labeled.  Thus, they can be updated in O(1){displaystyle O(1)} amortized time.See the list-labeling problem for details of both solutions.Order[edit]Given the sublist nodes X and Y, order(X, Y) can beanswered by first checking if the two nodes are in the samesublist. If so, their order can be determined by comparing their locallabels. Otherwise the labels of their representatives in the first list-labeling problem are compared.These comparisons take constant time.Insert[edit]Given a new sublist node for X and a pointer to the sublist node Y,insert(X, Y) inserts X immediately after Y in the sublistof Y, if there is room for X in the list, that is if the length of the list is no greater than 2log\u2061N{displaystyle 2log N} after the insertion.  It’s local label is given by the local list labeling algorithm for exponential labels.   This case takes O(1){displaystyle O(1)} amortized time.If the local list overflows, it is split evenly into two lists of size log\u2061N{displaystyle log N}, and the items in each list are given new labels from their (independent) ranges.  This creates a new sublist, which is inserted into the list of sublists, and the new sublist node is given a label in the list of sublists by the list-labeling algorithm.  Finally X is inserted into the appropriate list.This sequence of operations take O(log\u2061N){displaystyle O(log N)} time, but there have been \u03a9(log\u2061N){displaystyle Omega (log N)} insertions since the list was created or last split.  Thus the amortized time per insertion is O(1){displaystyle O(1)}.Delete[edit]Given a sublist node X to be deleted, delete(X) simplyremoves X from its sublist in constant time. If this leaves thesublist empty, then we need to remove the representative of thelist of sublists. Since at least \u03a9(log\u2061N){displaystyle Omega (log N)}elements were deleted from the sublist since it was first built we can afford to spend the O(log\u2061N){displaystyle O(log N)} time, the amortized cost of a deletion is O(1){displaystyle O(1)}.References[edit]^ Dietz, Paul F. (1982), “Maintaining order in a linked list”, Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC ’82), New York, NY, USA: ACM, pp.\u00a0122\u2013127, doi:10.1145\/800070.802184, ISBN\u00a0978-0897910705.^ Tsakalidis, Athanasios K. (1984), “Maintaining order in a generalized linked list”, Acta Informatica, 21 (1): 101\u2013112, doi:10.1007\/BF00289142, MR\u00a00747173.^ Dietz, P.; Sleator, D. (1987), “Two algorithms for maintaining order in a list”, Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC ’87), New York, NY, USA: ACM, pp.\u00a0365\u2013372, doi:10.1145\/28395.28434, ISBN\u00a0978-0897912211. Full version,Tech. Rep. CMU-CS-88-113, Carnegie MellonUniversity, 1988.^ A. Bender, Michael & Cole, Richard & Zito, Jack. (2004). Two Simplified Algorithms for Maintaining Order in a List. https:\/\/www.researchgate.net\/publication\/2865732_Two_Simplified_Algorithms_for_Maintaining_Order_in_a_List Retrieved 2019-06-14^ “File Maintenance: When in Doubt, Change the Layout!”, M. Bender, J. Fineman, S. Gilbert, T. Kopelowitz, P. Montes. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. eISBN\u00a0978-1-61197-478-2. https:\/\/doi.org\/10.1137\/1.9781611974782.98 Retrieved 2019-06-15^ Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E. (1989), “Making data structures persistent”, Journal of Computer and System Sciences, 38 (1): 86\u2013124, doi:10.1016\/0022-0000(89)90034-2, MR\u00a00990051.^ Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon (1997), “Sparsification\u2014a technique for speeding up dynamic graph algorithms”, Journal of the ACM, 44 (5): 669\u2013696, doi:10.1145\/265910.265914, MR\u00a01492341.^ Katriel, Irit; Bodlaender, Hans L. (2006), “Online topological ordering”, ACM Transactions on Algorithms, 2 (3): 364\u2013379, CiteSeerX\u00a010.1.1.78.7933, doi:10.1145\/1159892.1159896, MR\u00a02253786.^ Aumann, Yonatan; Bender, Michael A. (1996), “Fault tolerant data structures”, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996), pp.\u00a0580\u2013589, doi:10.1109\/SFCS.1996.548517, ISBN\u00a0978-0-8186-7594-2.^ Itai, Alon; Konheim, Alan G.; Rodeh, Michael (1981), “A Sparse Table Implementation of Priority Queues”, ICALP, pp.\u00a0417\u2013431^ Bul\u00e1nek, Jan; Kouck\u00fd, Michal; Saks, Michael E. (2015), “Tight Lower Bounds for the Online Labeling Problem”, SIAM Journal on Computing, vol.\u00a044, pp.\u00a01765–1797.External links[edit]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/order-maintenance-problem-wikipedia\/#breadcrumbitem","name":"Order-maintenance problem – Wikipedia"}}]}]