A well neglected data structure

I've been reading up on data structures and algorithms for a long time, as a database and data representation nerd. Especially with those having to do with relational databases and external memory overall. Every now and then one of them strikes me as being brilliant. Some of them even seem useful and elegant.

One structure which fills all of the prerequisites is the compact 0-complete tree. In principle, it is a self-balancing, variable arity search tree, much akin to B+ and splay trees. It's also compactly coded, which is nice. But the true revelation behind it is even more profound: in order to do a tree search, you do not need to store entire key values in the tree, but only the minimal binary decision points that are relevant. You can also construct a dynamically binning, self-balanced tree algorithm on top of that.

This means that the tree can depend pretty much on the total cardinality of the search space, and be asymptotically independent of key length. While remaining efficient even for external memory indexing, such as that we do within databases. Plus it implies the possibility of efficiently compressing arbitrary length keys into a fixed space, as long as the latter can enumerate the entire key space at any one time. (Here we do require the tree of decision points as side data, but with proper encoding that grows in an o(n log n) fashion with a very low multiplicative coefficient, by comparison with more well known trees.)

I find it truly exceptional that this reasoning hasn't been actively utilized in commercial databases, because it leads to amazingly space efficient, high fanout search trees. Also, it's almost insane that the compressive implication hasn't been exploited e.g. in routing hardware: such compression would preserve both strict lexical order and binary prefix-routability. This, despite the original paper having been published in a prestigious Proceedings, and it being from '88.

There are pretty much just two other papers in data structures which I'd rank this high, that I know of. One is Ailamaki et al's analysis on the practical multidimensionality of modern hard drives. And the other, one paper I saw on how to do multicolumn array search in equal complexity over all of the columns (I haven't been able to find it afterwards). Of those only Ailamaki's group actually came up with something clearly applicable.

How on earth could it be that these sorts of brilliant algorithms could be overlooked for over two decades, despite being publicly available, well documented, and clearly applicable even as such? To my eye it seems like more than one Second Coming suddenly went thoroughly unnoticed.

"Collateral damage"

The primary site of the German Pirate Party has been taken down, a mere two days before a state election. But not because of any wrongdoing on their part. Rather it seems that the servers, in full, were taken because somebody else was using them for alledgedly illegal purposes as well.

This sort of thing seems to become more and more common nowadays. The police can't disentangle digital wrong-doing from the right kind. So they wholesale confiscate everything in sight, with massive collateral damage. In this case endangering a political party's success in an open and democratic election.

This is far out of the norm, of course. Usually what is endangered in a wide search such as this has nothing to do with political parties. It has to do with individual, familial and small corporate interests. As such most of the searches go unnoticed and unpublished.

But these silent violations of the right to property, privacy and entrepreneurship entail the worst chilling factor ever imagined: while wholesale confiscation and long delays in the processing of digital assets are in themselves punitive and arbitrary, this sort of collateral confiscation means that you can't even deal with other people who might, potentially, be serving something other than kids cartoons.

In theory this is a procedural misstep which could be averted by copying all data in situ and leaving the servers to run. In practice, due to the unprofessionalism and/or vindictive nature of law enforcement, this amounts to a true chilling effect.

From encounters within my own social circuit in Finland, I can also guarantee that this isn't an isolated incident. This happens everywhere, and the costs of the intervention aren't being minimized. Thus, I have to call this a travesty.

Oikeus yksityisyyteen

Taannoisessa Mafian tapaamisessa päädyimme keskusteluun yksityisyydensuojasta. En ollut aiemmin ajatellut, että moinen voisi olla erillinen liberaali periaate. Mutta kun nyt olen alkanut uskoa siihen, että oikeustaloustiede lienee yksi parhaista tavoista erottaa käyvät oikeudet käymättömistä, minut on taidettu sitä kautta käännyttää yksityisyydensuojan kannattajaksi.

Perusesimerkkinä oli Googlen kamera, joka vilkuili ihmisten aitojen yli. Saako noin katsella, vapaasti? Aiemmin olin sitä mieltä, että totta kai saa. Jollei halua tulla nähdyksi, pitää pysyä sisätiloissa. Mutta tosiaan, aika kallistahan se on suojautua joka puolelta näkemiseltä. Ylhäältäkin kun voi olla pilvenpiirtäjä vieressä, ja varsinkin satelliitilta joka kuvaa suoraan ylhäältä. Infrapunakameralta viime kädessä, joka näkee osin seinän läpi.

Ilman moista teknologiaa se riittäisi, että rakennetaan muuri tai pannaan verhot kiinni. Mutta tuon teknologian kanssa aletaan päätyä tilanteisiin, joissa on yhtäkkiä paljon kalliimpaa suojata yksityisyyttään suhteessa aiempaan tai varsinkin suhteessa kuvaajan kuluihin. Edes itselle arvokas yksityisyys ei ole suojattavissa, neuvoteltavissa, tai varsinkaan tehokkaasti neuvoteltavissa kun lauma läpivalaisukykyisiä paparazzeja saapuu paikalle.

Tuolloin päädytään oikeustaloudellisesti katsoen ongelmaan, jossa tehokkuus ei enää toteudu vain sillä että maksaminen allokoidaan "kuvauksen uhrille". Yhtäkkiä onkin järkevää kääntää taakka niin, että on oikeus yksityisyyteen, ja kuvaajan tulee erityisesti sopia/maksaa kuvattavalle. Nimenomaan sen takia, että teknologia on tehnyt suhteessa helpommaksi rikkoa yksityisyyttä kaipaavan haluja, ja kasvattanut myös transaktiokuluja niin että Coasen teoreemankin nojalla oletussääntöä tulisi muuttaa.

Joten, taidan kannattaa jonkinasteista yksityisyydensuojaa, yhtäkkiä. Järkitililläni. Se mun toinen aivolohko edelleen sanoo, että kaiken tiedon pitäisi olla täysin vapaata, ongelmineenkin; se mun luonnonoikeuspainotteisempi...

Tämä päättely ei kuitenkaan edelleenkään nähdäkseni muuta sitä kuinka liberaali tai illiberaali olen. Nimittäin, liberaalille on tärkeää, että a) on niin suuri valta omiin asioihin kuin mahdollista, b) ilman että loukataan tuolla vallalla muiden vastaavaa vapautta omiin asioihinsa. Tuo aina jättää tietyn harmaan alueen, jonka Coasen teoreema formalisoi, ja jonka tulkinnasta tässä tapellaan. Sen sijaan useimmat yksilönvapauteen liittyvät perusasiat ovat edelleen pitkälti väittelyn tuollapuolen, kun niistä jo tiedetään, että viimeistään lähitulevaisuudessa sen enempää tiukka luonnonoikeudellinen kuin utilitaristinenkaan/kontraktaristinenkaan ajatustapa eivät muuta niitä. Tyyliin, ihmisen omistajuus omaisuuteensa, yksilön itsehallinto, tai sopimusinstituutio, NAP:in kolmena perusosana.

Tuollaisia perusasioita muuttaisi vasta teknologia, joka tekee kuolemasta kivutonta ja muutenkin irrelevanttia, omaisuudesta irrelevanttia omalle pärjäämiselle sekä kannustimille kautta laidan, ja ihmisluonnosta sellaista että kaikki yhteisöllisen toiminnan ongelmat joihin nykyään tarvitaan sopimuksia ratkaisemaan ne tulisivat jotenkin automaattisesti ja kautta ajan halutuiksi, ilman ulkopuolisen valvoman sopimusten luomaa kannustinta.

Moinen teknologia ei ole tulossa ihan huomenna, joten nuo kolme simppeleintäkin libertaaripeukalosääntöä pysyvät voimassa hamaan tulevaisuuteen, hyvän yhteiskunnan rakennusaineksena. Ja jos sitten sattumalta joku päivä sattumalta syntyisikin semmoista scifi-teknologiaa, joka järkyttää näitä olettamuksia (kuten transhumanistien povaama kivuton kuolema ja uploadin takaama jatkuva backup omalle mielelle, samaan aikaan)... Sitten "murha" ei ehkä enää ole kuin rikesakon arvoinen teko, mutta sekin seuraa edelleen täysin liberaaleista periaatteista tuossa ympäristössä, ja se Oikea Murha jossa tuhotaan myös sun backup ja/tai pakotetaan jokin sun kopio kuolemaan kivuliaasti edelleen samoin periaattein pysyy merkittävänä rikoksena.

Minusta tuo scifi-ajattelu kertoo aika hyvin, kuinka kantavaa liberaali poliittinen ajattelu itse asiassa on: se kantoi meidät kuninkaanvallasta teollistumiseen, sitten tasoitti kansallisvaltioita, kantoipa meidät tietoyhteiskuntaankin enemmän kuin yhdellä tavalla, ja luultavasti kantaisi meidät myös post-/transhumanistiseen raamiin, ilman että perusperiaatteet muuttuvat olennaisesti. Käytännön politiikka voi muuttua ja sen pitääkin, kun teknologia kehittyy. Mutta perusperiaatteet—ymmärrys yksilön tarpeista ja hänen suhteistaan yhteiskuntaan, sekä niistä seuraavista kannustimista ja niiden toteuttamiseen vaadittavasta formaalista laista—eivät juurikaan muutu eikä niiden tarvitse. Jollemme me nyt sitten ihmisinä muutu radikaalisti, yhtäkkiä.

Jopa pahimman scifi-friikin on vaikea keksiä tilanteita joissa liberaalit perusolettamat eivät olisi se parhain rakennusaines yhteiskunnalle, sanotaanko 10000 vuotta tulevaisuuteen. Tuohon vaadittaisiin oikeastaan se, että nopealla tahdilla muuttaisimme tarkoituksellisesti, geenitekniikan ynnä muun kautta, itsemme käyttäytymään kuin jokin sosiaalinen hyönteislaji. Vaan kuka hullu sellaistakaan haluaisi yrittää? Kyllä meillä nykyään menee paljon paremmin kuin muurahaisilla tai mehiläisillä, juurikin koska yksilöllisyytemme on sopivassa tasapainossa tuon yhteisöllisyyden kanssa; ja koska seuraamme pitkälti liberaaleja poliittisia periaatteita, jotka sovittavat nuo melko hyvin yhteen.

Metal children

This is the quintessential Finnish thing. Social democratic boredom, compensated by death metal and a deep-seated scepticism towards religion; that's what a state church tends to produce. The nihilism then seeps onto even children via their parents. With the children totally liking it, all the way. They really do like to burn a church or a crutch, or two Well down, as would I.

Bill O'Reilly would prolly choke on the indignation and his provincial win on this one. But I just think he doesn't have the speakers or the campy hard metal attitude to bring it down for real. For example, would he really be able to understand that it's a sketch, with a sequel to follow?

I don't think most political pundits would be ready to come onto the scene and follow the culture they themselves advocate so easily if they took these two seriously. Church-burning and anti-guncontrol in one fell swoop. With a little girl (?) *very* much liking it all.

Also, in O'Reilly's case, he could easily travel into Helsinki, Finland, and buy a triple-day pass into the Tuska (lit. "Agony") Festival, with all of the hard metal and these kinds of metal minded little kids around. With *none* of the disturbances that usually go along with festivals. With total gun-control as well. And really, parents and children with literally this sort of face color, basically having a loud picnic for one day of the year.

Factually speaking, Finnish Death Metal Children are far better off than the American, Bored, Suburban ones. The problem isn't about burning churches, or gun control. Much less gyn control. The problem is about not being connected to your parents and/or friends. About not having a fulfilling childhood and/or surrounding community.

Pride-iskun tuomio on riittämätön

Viime kesän Helsinki Pride -kulkueeseen kohdistuneen kaasuiskun tuomio saapui vihdoin, yllättävänkin nopeasti. Vaikka yleensä olenkin hyvin lievän rangaistuskäytännön kannattaja, tässä nimenomaisessa tapauksessa katson, että neljän kuukauden ehdollinen vankeusrangaistus pahoinpitelystä on selvästi riittämätön. Kun olen aiemmin jo kirjoittanut rangaistusten määräytymisperusteista toisessa yhteydessä, yritän perustella väitteeni tuota postia vasten.

Pahin ja tärkein virhe tuomiossa nähdäkseni on takertuminen yksittäisen teon lailliseen kuvaukseen, ja yksittäisen uhrin kokemaan haittaan. Tästä on seurannut iskun luokittelu ensi sijassa pahoinpitelyksi, ja sitä kautta pitäytyminen tyypillisen pahoinpitelyn rangaistusasteikkoon sekä suuren uhrijoukon käsittely kuitenkin yhtenä pahoinpitelytyyppisenä tekona.

Tämä on ongelmallista, koska tyypillinen pahoinpitely on yhden ihmisen pikaistuksissaan toteuttama nyrkkitappelu. Sen rangaistusasteikko on alhainen pääasiassa siksi, että teko on hankalasti ehkäistävissä rangaistuksin tunnekuohun tähden, ja se on myös sillä tavalla yksityinen teko etteivät sosiaaliset mekanismit kykene paljon vaikuttamaan teon todennäköisyyteen. Pride-isku oli molemmissa suhteissa täysin päinvastainen: tuomioistuinkin totesi, että yhtenäinen vaatetus, hankalastihankittavien luvattomien kaasuaseiden läsnäolo, hyvinorganisoitu poistuminen paikalta, synkronoidusti toimivien tekijöiden suuri määrä, tekijöiden ikä, ynnä muut tekijät, osoittivat selvää valmistautumista, järjestäytymistä ja etukäteisharkintaa. Tässä tilanteessa pitäisi olla täysin selvää, että rikostyyppi ei ole pikaistuksissa tehty vahinko jota itsekin aidosti kadutaan jälkeenpäin, vaan samalla tavalla suunnitelmallinen kuin vaikkapa talousrikollisuus, jota kadutaan vasta jos jäädään kiinni. Niinpä yleisehkäisevyyden nimissä rangaistusasteikon pitäisi olla samalla tavalla kovempi kuin "aitojen" valkokaulusrikosten on suhteessa tuottamukselliseen velallisen epärehellisyyteen, tai murhan tappoon. Meiltä vain puuttuu lainsäädännöstä erillinen kategoria suunnitelmalliselle pahoinpitelylle, toisin kuin "suunnitelmalliselle tapolle", eli siis murhalle.

Samalla tavalla meiltä puuttuu laista nähtävästi ajatus siitä, että järjestäytynyt teko, silloin kun sitä ei ole tehty suoranaisen jo tunnetun järjestäytyneen rikollisjärjestön aloitteesta, olisi erillinen rikoskategoria. Tyyliin "salaliitto" (vrt. jenkkien RICO-pykälä). On tietty totta, että moiset pykälät ovat usein ylimitoitettuja, ja voivat johtaa länsimaiselle oikeuskäytännölle vieraaseen yhteisölliseen vastuuseen. Mutta niissä on silti tietty totuuden siemen, joka meilläkin tavallisesti tunnustetaan täyden yhteisen, kertautuvan vastuun periaatteen kautta: järjestäytyminen ei ainakaan voi hämärtää syyllisyyttä joukossa. Ainakin minusta sen pitäisi lisäksi puhua erityisestä tarkoituksellisuudesta tai törkeydestä koventamisperusteena, ja luultavasti tuohon pitäisi liittää meillä ennen tuntematon erillinen, yhteisöllinen näkökulma, nimenomaan siksi että jos tosiaan on näytettävissä että rikolliset itse ovat valinneet tekevänsä teon yhteisöllisesti, silloin tietynasteinen yhteisöllinen vastuu heikentää täsmälleen tekijöiden eikä esimerkiksi muiden tietyn järjestön jäsenien keskinäistä koheesiota. Eli ei siis loukkaa mitään varsinaista oikeushyvää, mutta vähentää järjestäytyneen rikollisuuden mahdollisuuksia, kunhan vain tulkitsemme ajatuksen kapeasti.

Monet kaverini ovat sitä mieltä, että hyökkäys nimenomaan syrjittyä seksuaalivähemmistöä vastaan oli tässä se isoin ongelma. Suomen laki on osin samaa mieltä, kun puhuu "viharikoksesta" rangaistuksen koventamisperusteena, ja esim. listaa joukon ryhmiä joita vastaan ei saa kiihottaa. Tästä ajatuksesta olen hieman eri mieltä. Ongelma ei nimittäin nähdäkseni oikeustaloustieteellisesti ole se, että tietyt ryhmät kaipaavat erityissuojelua. Päin vastoin ongelma on siinä, että aivan kuten järjestäytyneessä rikollisuudessa tekijäosapuoli on järjestäytynyt, viharikollisuudessa uhrit ovat jokin selkeä ryhmä jota vastaan hyökätään. Silloin on nähdäkseni sama onko kohderyhmä homot vai perussuomalaiset; kysymys on ensi sijassa järjestäytymisestä kohteen mukaan, tekijän asemesta. Tämän periaatteen alla poliittisten toimintavapauksien haittaaminen, mielenosoitusoikeuden rikkomus, viharikokset, ja vaikkapa laiton vaalirahoitus ovat täysin samantyyppisiä tekoja, joilla pitäisi olla samanlainen koventava vaikutus tuomioon. Ongelma ei ole se että uhri on homo, ongelma on, että kyseessä on selvästi tunnistettava ryhmä jonka sosiaalista koheesiota tarkoituksellisesti haitataan. Kyseessä on pelkoon tähtäävä toiminta, joka on siinä määrin tunnistettavissa olevaan kohderyhmään kohdistuvaa, että se lisää pelottelun voimaa merkittävästi; ei aivan suora yksilökohtainen laiton uhkaus, mutta pitkän matkaa siihen suuntaan kuitenkin, ja rajoittavuudessaan jälleen harkittu, ei vain vahinko.

Tietysti tässä tapauksessa sekä tekijätaho että kohderyhmä olivat järjestäytyneitä. Meidän lakimme tuntee tuonkin tekotavan nimeltä: se on terrorismia. Tässä kohtaa hyvin matala-asteista suhteessa itsemurhapommeihin toki, mutta terroria silti. Eli olen hieman sitä mieltä, että Pride-iskua olisi pitänyt ihanteellisesti käsitellä osana terrorismin laajaa skaalaa, ei yksittäisinä pahoinpitelyinä. Jostain syystä vain laki ei tässäkään tunnista sitä tosiasiaa, että kaikista rikosnimikkeistä on olemassa esimerkkejä lähes harmittomasta aina pahimpaan mitä ihminen voi tehdä. Jos tämä tapaus olisi siis voitu käsitellä minimiterrorina, rikosrekisterimerkinnät olisivat heijastaneet pysyvyydeltään paremmin ja avoimemmin teon oikeaa luonnetta sekä tekijöiden myöhempää, spesifistä haittapotentiaalia.

Viimein täytyy sanoa sananen korvauksista. Monet kaverini ovat olleet tyytyväisiä siitä, että ainakin korvauksia jaettiin niin paljon. Tämä ajatusmalli on mielestäni huono. Kuten olen aiemminkin sanonut, korvauksia pitäisi määrätä selvästä haitasta, joka tässä on ollut varsin pieni suhteessa esimerkiksi murtuneeseen nenään nakkikioskitappelussa. Kaikki lääkärikulut ja muut ovat itsestäänselviä, mutta kivut ja säryt ovat olleet lähestulkoon olemattomia; täysin verrattavissa esimerkiksi savuhaittaan laajasta, luvattomasta metsänkulotuksesta. Tuolloin korvauksia ei tulisi määrätä epäsuhdassa, eli luultavasti niitä ei tulisi useimmille uhreille tulla kuin korkeintaan kymmeniä euroja.

Koska tuomion tulisi painottaa siis ennaltaehkäisyä rikostyypissä joka on erityisen ennaltaehkäistävä, nähdäkseni oikea tuomio olisi ollut yhteinen 2-4kk ehdotonta vankeutta ensikertalaisille tekijöille, tuomion olisi pitänyt tulla jostakin terrorismiin verrattavasta teosta jonka vanhenemisaika on pitkä (niin että juttu pysyy auki muiden salaliittolaisten kiinnisaamiseksi ja teon tarkoituksellinen luonne järjestelmässä tallessa), sen olisi pitänyt tulla paljon nopeammin kuin se nyt tuli, korvausten olisi pitänyt pitäytyä nykyistä pienempinä ja yhteisvastuullisina kun teon suunnittelukin selvästi oli sitä, ja noinkin lyhyeen tuomioon olisi pitänyt voida liittää esim. 90 päiväsakon kokoinen yhteisvastuullinen oheissakko per tekijä (toteamalla in absentia että samaa sovelletaan myöhemmin kiinnijääneisiin salaliiton jäseniin) jotta.valtaosa tuomiosta koostuisi itse asiassa harmaanikävästä työnteosta laajemman yhteiskunnan hyväksi.