7
$\begingroup$

What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move items in the list. Occasionally they will be online to synchronize the list. The algorithm should minimize the amount of changed items or "diffs" that need to be communicated.

For an unordered list we would simply use a modification timestamp and UUID for each item to detect edits respectively inserts/deletions. But what data structure can we use for an ordered list? Using an integer rank would require renumbering all successors after an insert, and thus result in many "diffs" when comparing items in both lists. Using a floating-point rank (having the average of the predecessor and successor ranks) would have accuracy problems after inserting many new items.

Using a doubly linked list (i.e. referencing the UUID of the predecessor and successor item) would result in two changed items and one new item for each insert, thus 3 "diffs" when comparing items in both lists.

Any suggestions, pointers to literature or Google search terms about this subject?

$\endgroup$
  • $\begingroup$ Do you want to recognize moves? First you say yes, then no. $\endgroup$ – reinierpost Apr 13 '12 at 9:08
  • $\begingroup$ One idea is to regard the specification of the ordering as a separate item, like filesystems do, and synchronize that as well. $\endgroup$ – reinierpost Apr 13 '12 at 9:11
  • $\begingroup$ Yes, I want to recognize moves. I'd prefer a solution with only one type of items, not content-items and order-items. $\endgroup$ – Jason Smith Apr 13 '12 at 15:01
  • $\begingroup$ Your question is related to one I asked myself a couple of years ago: what existing theory can be applied to developing a diff that will recognize moves and file renames? But I never tried to answer that question. One idea is to look at algorithms used by software such as git. $\endgroup$ – reinierpost Apr 16 '12 at 9:55
  • $\begingroup$ Mercurial (Hg) recognizes moves and renames by calculating how similar files are. If they match more than, say, 90% they are probably moved/renamed. I am not sure what algorithm they use to calculate the percentage (e.g. Levenshtein distance). That occasionally results in false positives. Since I have both lists, I can do a direct diffs and recognize changes 100% accurately. I am looking for a way to limit the number of diffs to only the items that actually changed (and not its predecessor or successor). $\endgroup$ – Jason Smith Apr 16 '12 at 15:19
2
$\begingroup$

For synchronizing from a master list to a slave list, it looks like a fellow named Michael Heyeck has a good, O(n) solution to this problem. Check out that blog post for an explanation and some code. Perhaps this is a good starting point to generalize to a two-way sync.

Essentially, the solution tracks both the master and slave lists in a single pass, tracking indices into each. Two data structures are then managed: a list of insertions to be replayed on the slave list, and a list of deletions.

It looks straightforward and also has the benefit of a proof of minimalism, which Heyeck followed up with in a subsequent post. The code snippet in this post is more compact, as well:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x < len(a)) or (y < len(b)):
    if y >= len(b): d.append(x); x += 1
    elif x >= len(a): i.append((y, b[y])); y += 1
    elif a[x] < b[y]: d.append(x); x += 1
    elif a[x] > b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)

Again, credit to Michael Heyeck.

$\endgroup$
0
$\begingroup$

The standard approach is probably going to be something like this:

  • Each side keeps track of the last-synchronized state of the list. In other words, at any point in time, each side knows the state $L_{t-1}$ of the list at the last synchronization point when they synchronized their lists.

  • If Alice currently has list $L$ and she wants to send her updates to Bob, she computes the diff between $L_{t-1}$ and $L$ and sends that diff to Bob.

  • If both Alice and Bob concurrently made changes to their list, then you need to merge their diffs to form a new list.

  • The result, after sychronization is $L_t$, which is known to both parties. Now go back to the beginning.

Now you have some design decisions that you can fill in various ways:

  • How should Alice compute the diff between $L_{t-1}$ and her list $L$? One way is for her to keep track of a log of the changes she has made to the list since $L_{t-1}$ and use that as the diff (or possibly to compact that diff, e.g., if she inserts an item and then deletes it, no need to include that in the log of changes). Another way is for her to compute the diff between $L_{t-1}$ and $L$ from scratch, without keeping any logs.

  • How should the diff be represented compactly, to minimize network bandwidth and make it as easy as possible for Bob to apply the diff?

  • How should we merge Alice's diff and Bob's diff? There are many standard algorithms here; e.g., see source code revision control systems.

I hope that this was not already obvious. Your question did not make it entirely clear how much you already know about the general approach and what specifically you were looking for in an answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.