Subject: Re: [alto] The size of the cost map

From: Wendy Roome <[email-masked]>
Date: Fri, 22 Mar 2013 15:34:16 -0400

As Sebastian points out, sparse cost maps are allowed, and if the map is
sparse, it's reasonable to have a large number of PIDs.

But there's a gotcha. Remember clients must store the cost map, and lookup
costs as needed. If the client knows the matrix is sparse, the client can
store it as a hash table, where the key is the concatenation of the source
& dest PID names. That's simple & efficient.

Unfortunately, if the matrix ISN'T sparse, that technique is horribly
inefficient. If the matrix is full, the client should convert pid names to
index numbers (sort the PID names, use binary search to get the index),
and then store the costs in a conventional float[N][N] array.

And, of course, that technique is wasteful for a sparse cost matrix.

So the client has to guess how "sparse" the cost matrix really is.

	- Wendy Roome

>Message: 2
>Date: Fri, 22 Mar 2013 08:30:14 +0100
>From: Sebastian Kiesel <[email-masked]>
>To: [email-masked]
>Subject: [alto] The size of the cost map
>Message-ID: <[email-masked]>
>Content-Type: text/plain; charset=us-ascii
>
>Hi,
>
>lately we've been discussing linear vs. quadratic growth of the cost map,
>but at least I had no real feeling what this means in terms of bytes on
>the wire, using our JSON encoding. So I made a short experiment that I
>want to share:
>

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 25 Mar 2013 09:38:32 +0100

Wendy,

> & dest PID names. That's simple & efficient.

I agree.

> and then store the costs in a conventional float[N][N] array.

Could this be done on the fly while reading the JSON data structures
from the network? ...

> So the client has to guess how "sparse" the cost matrix really is.

... or do I have to read all the JSON stuff into a temporary buffer,
then decide whether to go for a hash or an array. If the array, do
pid name -> index mapping, identify the highest index, allocate array
and eventually fill it? That would be 3 passes or more?

Thanks
Sebastian

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Mon, 25 Mar 2013 10:42:26 +0100

> > inefficient. If the matrix is full, the client should convert pid 
> > names to index numbers (sort the PID names, use binary 
> search to get 
> > the index), and then store the costs in a conventional 
> float[N][N] array.
> 
> Could this be done on the fly while reading the JSON data 
> structures from the network? ...

Is there an existing JSON parser libary that supports such "on-the-fly" parsing (stream-like)?

The libraries I have looked at so far typically parse a buffer with the whole JSON data. 
 
> ... or do I have to read all the JSON stuff into a temporary 
> buffer, then decide whether to go for a hash or an array. If 
> the array, do pid name -> index mapping, identify the highest 
> index, allocate array and eventually fill it? That would be 3 
> passes or more?

Out of my head, I'd think that multiple passes will be needed when using standard JSON libraries. Obviously, an ALTO implementation can implement own JSON parsing logic, but we'd better not assume this.

Michael

---

From: Wendy Roome <[email-masked]>
Date: Mon, 25 Mar 2013 09:49:37 -0400

Okay, here's how a client can handle large cost maps whether they're
sparse or full.

First, get a sparse matrix class. It must handle square matrices with
numeric indexes, 0 to N-1, for a fixed N. The class should be efficient
(in space and time) whether the matrix is full or sparse.

I couldn't find a good sparse matrix class in java, so I wrote my own.
Also, it's difficult for me to use an open-source package. My employer
wants me to clear the license with our lawyers, to make sure it doesn't
restrict our right to use it in a product. And if I have to choose between
spending a day with a lawyer or a day writing code ....

Then get a on-the-fly parser class for JSON. Typically this has a base
scanner that calls abstract methods when it encounters a new list, an item
in a list, a new dictionary, an item in a dictionary, etc. I couldn't find
one of those either. Fortunately JSON is simple, so it's not hard to write
one.

Then write a class to convert the PID names to index numbers (given a
network map, save the PID names in an array, sort, then lookup name via
binary search).

Finally extend the on-the-fly parser to read a cost map response. When it
gets a cost, it converts the src & dest pid names to numbers and sets that
element in the sparse matrix.

So a client can read a possibly sparse matrix in one pass. But it requires
extra effort to write those classes, or locate ones that are acceptable.
Simple techniques will work fine for small ALTO servers, but then fail
miserably when confronted with a large server.

	- Wendy Roome

On 03/25/2013 05:42, "Scharf, Michael (Michael)"
<[email-masked]> wrote:

>Out of my head, I'd think that multiple passes will be needed when using
>standard JSON libraries. Obviously, an ALTO implementation can implement
>own JSON parsing logic, but we'd better not assume this.