[SciPy-user] Efficient submatrix of a sparse matrix

Brendan Simons brendansimons at yahoo.ca
Thu Sep 7 00:08:39 CDT 2006


Hi all,

I have a neat little problem for which I think sparse matrices are  
the answer.   I need to store a bunch of overlapping "intervals", (a,  
b pairs for which any a <= val < b crosses that interval) in a manner  
which makes "stabbing inquiries" (which intervals cross a specified  
value) easy.  The canonical way to to this is with interval trees (a  
good summary here: http://w3.jouy.inra.fr/unites/miaj/public/vigneron/ 
cs4235/l5cs4235.pdf), however I think I can simplify things as follows:

1)  perform an argsort on the interval a and b endpoints.  This gives  
the position of each interval in an "order" matrix M, where each row  
and each column contains only one interval, and intervals are sorted  
in rows by start point, and in columns by endpoint

2) for a "stab" point x, do a binary search to find the row i and  
column j where x could be inserted into M and maintain its ordering.   
The submatrix of M[:i, j:]  would contains all those intervals which  
start before x, and end after x.

Since the order matrix M is mostly empty it would make sense to use a  
sparse matrix storage scheme, however the only one in scipy.sparse  
that allows 2d slicing is the dok_matrix, and the slicing algorithm  
is O(n), which is much too expensive for my purposes (I have to do  
thousands of stabbing inquiries on a space containing thousands of  
intervals).

Is there no more efficient algorithm for 2d slicing of a sparse matrix?

   -Brendan
--
Brendan Simons
__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 


More information about the SciPy-user mailing list